{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Grid Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: gridGame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #网格游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的二维数组 <code>grid</code> ，数组大小为 <code>2 x n</code> ，其中 <code>grid[r][c]</code> 表示矩阵中 <code>(r, c)</code> 位置上的点数。现在有两个机器人正在矩阵上参与一场游戏。</p>\n",
    "\n",
    "<p>两个机器人初始位置都是 <code>(0, 0)</code> ，目标位置是 <code>(1, n-1)</code> 。每个机器人只会 <strong>向右</strong> (<code>(r, c)</code> 到 <code>(r, c + 1)</code>) 或 <strong>向下 </strong>(<code>(r, c)</code> 到 <code>(r + 1, c)</code>) 。</p>\n",
    "\n",
    "<p>游戏开始，<strong>第一个</strong> 机器人从 <code>(0, 0)</code> 移动到 <code>(1, n-1)</code> ，并收集路径上单元格的全部点数。对于路径上所有单元格 <code>(r, c)</code> ，途经后 <code>grid[r][c]</code> 会重置为 <code>0</code> 。然后，<strong>第二个</strong> 机器人从 <code>(0, 0)</code> 移动到 <code>(1, n-1)</code> ，同样收集路径上单元的全部点数。注意，它们的路径可能会存在相交的部分。</p>\n",
    "\n",
    "<p><strong>第一个</strong> 机器人想要打击竞争对手，使 <strong>第二个</strong> 机器人收集到的点数 <strong>最小化</strong> 。与此相对，<strong>第二个</strong> 机器人想要 <strong>最大化</strong> 自己收集到的点数。两个机器人都发挥出自己的 <strong>最佳水平</strong>&nbsp;的前提下，返回 <strong>第二个</strong> 机器人收集到的 <strong>点数</strong> <em>。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/08/a1.png\" style=\"width: 388px; height: 103px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[2,5,4],[1,5,1]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。\n",
    "第一个机器人访问过的单元格将会重置为 0 。\n",
    "第二个机器人将会收集到 0 + 0 + 4 + 0 = 4 个点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/08/a2.png\" style=\"width: 384px; height: 105px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[3,3,1],[8,5,2]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。 \n",
    "第一个机器人访问过的单元格将会重置为 0 。\n",
    "第二个机器人将会收集到 0 + 3 + 1 + 0 = 4 个点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/08/a3.png\" style=\"width: 493px; height: 103px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,3,1,15],[1,3,3,1]]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。\n",
    "第一个机器人访问过的单元格将会重置为 0 。\n",
    "第二个机器人将会收集到 0 + 1 + 3 + 3 + 0 = 7 个点。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>grid.length == 2</code></li>\n",
    "\t<li><code>n == grid[r].length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= grid[r][c] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [grid-game](https://leetcode.cn/problems/grid-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [grid-game](https://leetcode.cn/problems/grid-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,5,4],[1,5,1]]', '[[3,3,1],[8,5,2]]', '[[1,3,1,15],[1,3,3,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        sum_1 = sum(grid[0]) - grid[0][0]\n",
    "        ans = sum_1\n",
    "        sum_2 = 0\n",
    "        for i in range(1, n - 1):\n",
    "            sum_1 -= grid[0][i]\n",
    "            sum_2 += grid[1][i - 1]\n",
    "            if max(sum_1, sum_2) < ans:\n",
    "                ans = max(sum_1, sum_2)\n",
    "        sum_2 += grid[1][n - 2]\n",
    "        return min(ans, sum_2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        suf = sum(grid[0]) - grid[0][0]\n",
    "        pre = 0\n",
    "        s = [suf]\n",
    "        for i in range(n - 1):\n",
    "            pre += grid[1][i]\n",
    "            suf -= grid[0][i + 1]\n",
    "            s.append(max(pre, suf))\n",
    "        return min(s)\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        suf = sum(grid[0]) - grid[0][0]\n",
    "        pre = 0\n",
    "        s = suf\n",
    "        for i in range(n - 1):\n",
    "            pre += grid[1][i]\n",
    "            suf -= grid[0][i + 1]\n",
    "            s = min(s, max(pre, suf))\n",
    "        return s\n",
    "\n",
    "\n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        ans = inf \n",
    "        left0 = sum(grid[0])\n",
    "        left1 = 0\n",
    "        for j, v in enumerate(grid[0]):\n",
    "            left0 -= v \n",
    "            ans = min(ans, max(left0,left1))\n",
    "            left1 += grid[1][j]\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        length = len(grid[0])\n",
    "        if length <=1:\n",
    "            return 0\n",
    "        sumFromLeft = sum(grid[1][:-1])\n",
    "        sumFromRight = 0\n",
    "        min2Sum = sumFromLeft + sumFromRight\n",
    "        for idx in range(length - 2, -1, -1):\n",
    "            sumFromLeft -= grid[1][idx]\n",
    "            sumFromRight += grid[0][idx+1]\n",
    "            min2Sum = min(min2Sum, max(sumFromLeft, sumFromRight))\n",
    "        return min2Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        result = float(\"inf\")\n",
    "        length = len(grid[0])\n",
    "        left, right = 0, sum(grid[0])\n",
    "        for i in range(length):\n",
    "            right -= grid[0][i]\n",
    "            result = min(result, max(left, right)) \n",
    "            left += grid[1][i]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        s0 = 0\n",
    "        ret = s1 = sum(grid[1]) - grid[1][-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            s1 -= grid[1][i]\n",
    "            s0 += grid[0][i+1]\n",
    "            cur = max(s1, s0)\n",
    "            if ret > cur:\n",
    "                ret = cur\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def gridGame(self, grid: List[List[int]]) -> int:\n",
    "#         n = len(grid[0])\n",
    "#         suf = sum(grid[0]) - grid[0][0]\n",
    "#         pre = 0\n",
    "#         s = [suf]\n",
    "#         for i in range(n - 1):\n",
    "#             pre += grid[1][i]\n",
    "#             suf -= grid[0][i + 1]\n",
    "#             s.append(max(pre, suf))\n",
    "#         return min(s)\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        suf = sum(grid[0]) - grid[0][0]\n",
    "        pre = 0\n",
    "        s = suf\n",
    "        for i in range(n - 1):\n",
    "            pre += grid[1][i]\n",
    "            suf -= grid[0][i + 1]\n",
    "            s = min(s, max(pre, suf))\n",
    "        return s\n",
    "\n",
    "\n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid[0])\n",
    "        if n==1:\n",
    "            return 0 \n",
    "        s0=0\n",
    "        s1=sum(grid[0][1:])\n",
    "        ans=s1\n",
    "        for i in range(n-1):\n",
    "            \n",
    "            s0+=grid[1][i]\n",
    "            s1-=grid[0][i+1]\n",
    "            ans=min(ans,max(s0,s1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        result = []\n",
    "        up_right = sum(grid[0]) - grid[0][0]\n",
    "        down_left = 0\n",
    "        result.append(max(up_right, down_left))\n",
    "        for i in range(1, len(grid[0])):\n",
    "            up_right -= grid[0][i]\n",
    "            down_left += grid[1][i - 1]\n",
    "            print(up_right, down_left)\n",
    "            result.append(max(up_right, down_left))\n",
    "        return min(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        # 前缀和\n",
    "        ans = float('inf')\n",
    "        s1 = 0\n",
    "        for v in grid[0]:\n",
    "            s1 += v\n",
    "        s2 = 0\n",
    "        for i, v in enumerate(grid[0]):     # 枚举第一个机器人的拐弯位置\n",
    "            s1 -= v\n",
    "            ans = min(ans, max(s1, s2))\n",
    "            s2 += grid[1][i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys        \n",
    "        \n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        upper = grid[0]\n",
    "        lower = grid[1]\n",
    "       # result = []\n",
    "        n = len(upper)\n",
    "        result_max = sys.maxsize\n",
    "        for i in range(n):\n",
    "            if i==0:\n",
    "                upper_max = sum(upper[1:])\n",
    "                lower_max = 0\n",
    "            else:\n",
    "                upper_max -= upper[i]\n",
    "                lower_max += lower[i-1]\n",
    "                \n",
    "            if upper_max > lower_max:\n",
    "                if upper_max < result_max:\n",
    "                    result_max = upper_max\n",
    "            else:\n",
    "                if lower_max < result_max:\n",
    "                    result_max = lower_max\n",
    "            a = 1\n",
    "                \n",
    "        return result_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        ans = float('inf')\n",
    "        s1 = sum(grid[0])\n",
    "        s2 = 0\n",
    "        n = len(grid[0])\n",
    "        for i in range(n):\n",
    "            s1 -= grid[0][i]\n",
    "            if i > 0:\n",
    "                s2 += grid[1][i-1]\n",
    "            ans = min(ans, max(s1,s2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        result = []\n",
    "        up_right = sum(grid[0]) - grid[0][0]\n",
    "        down_left = 0\n",
    "        result.append(max(up_right, down_left))\n",
    "        for i in range(1, len(grid[0])):\n",
    "            up_right -= grid[0][i]\n",
    "            down_left += grid[1][i - 1]\n",
    "            print(up_right, down_left)\n",
    "            result.append(max(up_right, down_left))\n",
    "        return min(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        res, upper, down = inf, sum(grid[0]), -grid[1][-1]\n",
    "        for p in range(len(grid[0])):\n",
    "            upper -= grid[0][p]\n",
    "            down += grid[1][p-1]\n",
    "            res = min(res, max(upper, down))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        first, second = sum(grid[0]), 0\n",
    "        ret = float('inf')\n",
    "        for i in range(len(grid[0])):\n",
    "            first -= grid[0][i]\n",
    "            ret = min(ret, max(first, second))\n",
    "            second += grid[1][i]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        ans = inf\n",
    "        up = 0\n",
    "        for v in grid[0]:\n",
    "            up += v\n",
    "        down = 0\n",
    "        for j, v in enumerate(grid[0]):\n",
    "            up -= v\n",
    "            ans = min(ans, max(up, down))\n",
    "            down += grid[1][j]\n",
    "        return ans\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        i = n//2\n",
    "        a = sum(grid[0][i+1:])\n",
    "        b = sum(grid[1][:i])\n",
    "        if a == b:\n",
    "            return a\n",
    "        elif a>b:\n",
    "            while a>b and i<n:\n",
    "                a = a - grid[0][i+1]\n",
    "                b = b + grid[1][i]\n",
    "                i+=1\n",
    "            return min(max(a,b),max(a+grid[0][i],b-grid[1][i-1]))\n",
    "        else:\n",
    "            while b>a and i >=0:\n",
    "                a = a + grid[0][i]\n",
    "                b = b - grid[1][i-1]\n",
    "                i-=1\n",
    "            return min(max(a,b),max(a-grid[0][i+1],b+grid[1][i]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        w = len(grid[0])\n",
    "        first_sum = sum(grid[0][1:])\n",
    "        second_sum = 0\n",
    "        res = first_sum\n",
    "        for i in range(w-1):\n",
    "            first_sum -= grid[0][i+1]\n",
    "            second_sum += grid[1][i]\n",
    "            res = min(res, max(first_sum, second_sum))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        pre0, pre1 = 0, 0\n",
    "        pre0 = sum(v for i, v in enumerate(grid[0]))\n",
    "        ans = pre0\n",
    "        for i, v in enumerate(grid[0]):\n",
    "            pre0 -= v\n",
    "            ans = min(ans, max(pre0, pre1))\n",
    "            pre1 += grid[1][i]\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        top, bottom = sum(grid[0][1:]), 0\n",
    "        res = top\n",
    "        for i in range(1, len(grid[0])):\n",
    "            top -= grid[0][i]\n",
    "            bottom += grid[1][i-1]\n",
    "            res = min(res, max(top, bottom))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 枚举第一个机器人的拐弯位置\n",
    "    # 由于矩阵只有两行，我们可以枚举第一个机器人的拐弯位置，于是剩余的点数被划分成了两部分，即第一行的后缀和第二行的前缀，另一个机器人只能在这两部分中取最大值。为了最小化第二个机器人收集的点数，取所有最大值中的最小值，即为答案。\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        ans = float('inf')\n",
    "        left0 = sum(grid[0])\n",
    "\n",
    "        left1 = 0\n",
    "\n",
    "        for j, v in enumerate(grid[0]):\n",
    "            left0 -= v\n",
    "            ans = min(ans, max(left0, left1))\n",
    "            left1 += grid[1][j]\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        num = len(grid[0])\n",
    "\n",
    "        pres0 = [0] * num\n",
    "        curr_sum = 0\n",
    "        for i in range(num - 1, 0, -1):\n",
    "            curr_sum += grid[0][i]\n",
    "            pres0[i - 1] = curr_sum\n",
    "\n",
    "        pres1 = [0] * num\n",
    "        curr_sum = 0\n",
    "        for i in range(0, num - 1):\n",
    "            curr_sum += grid[1][i]\n",
    "            pres1[i + 1] = curr_sum\n",
    "\n",
    "        return min(max(pre0, pre1) for pre0, pre1 in zip(pres0, pres1))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        r1,r2 = [0]*n,[0]*n\n",
    "        for i in range(n-1,0,-1):r1[i-1] = r1[i]+grid[0][i]\n",
    "        for i in range(n-1):r2[i+1] = r2[i]+grid[1][i]\n",
    "        res = float('inf')\n",
    "        for i in range(n):res = min(res,max(r1[i],r2[i]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        dp0 = [0] * (n + 1)\n",
    "        dp1 = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp0[i] = dp0[i - 1] + grid[0][i - 1]\n",
    "            dp1[i] = dp1[i - 1] + grid[1][i - 1]\n",
    "        ans = math.inf\n",
    "        for i in range(1, n + 1):\n",
    "            ans = min(ans, max(dp0[n] - dp0[i], dp1[i - 1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "\n",
    "        # r1和r2分别存储第一行和第二行的前缀和\n",
    "        r1, r2 = [0]*n, [0]*n\n",
    "\n",
    "        # 计算第一行从右到左的前缀和\n",
    "        for i in range(n-1, 0, -1):\n",
    "            r1[i-1] = r1[i] + grid[0][i]\n",
    "        \n",
    "        # 计算第二行从左到右的前缀和\n",
    "        for i in range(n-1):\n",
    "            r2[i+1] = r2[i] + grid[1][i]\n",
    "        \n",
    "        # 初始化结果为正无穷，因为我们要找的是最小值\n",
    "        res = float('inf')\n",
    "\n",
    "        # 对于每个位置i，我们计算第一个机器人在该位置向下时，第二个机器人能够获得的最大得分\n",
    "        for i in range(n):\n",
    "            res = min(res, max(r1[i], r2[i]))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        first_row_left_sum = [0] * n\n",
    "        second_row_right_sum = [0] * n\n",
    "        sum = 0\n",
    "        for i in range(n):\n",
    "            sum += grid[0][i]\n",
    "            first_row_left_sum[i] = sum\n",
    "\n",
    "        sum = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            sum += grid[1][i]\n",
    "            second_row_right_sum[i] = sum\n",
    "\n",
    "        ret_score = first_row_left_sum[0] + second_row_right_sum[0]\n",
    "        for i in range(n):\n",
    "            ret_score = min(\n",
    "                ret_score,\n",
    "                max(\n",
    "                    first_row_left_sum[-1] - first_row_left_sum[i],\n",
    "                    second_row_right_sum[0] - second_row_right_sum[i]\n",
    "                )\n",
    "            )\n",
    "        return ret_score\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        r1 = [0]*len(grid[0])\n",
    "        r2 = [0]*len(grid[0])\n",
    "        for j in range(len(grid[0])):\n",
    "            if j == 0:\n",
    "                r1[j] = grid[0][j]\n",
    "                r2[j] = grid[1][j]\n",
    "            else:\n",
    "                r1[j] = r1[j-1]+grid[0][j]\n",
    "                r2[j] = r2[j-1]+grid[1][j]\n",
    "        a = -1\n",
    "        b = -1\n",
    "        t = r1[-1] + r2[-1]\n",
    "        for j in range(len(grid[0])):\n",
    "            if j == 0:\n",
    "                a = r1[-1] - r1[0]\n",
    "                b = 0\n",
    "            else:\n",
    "                a = r1[-1] - r1[j]\n",
    "                b = r2[j-1]\n",
    "            #print(j, a, b)\n",
    "            t = min(t, max(a,b))\n",
    "        return t\n",
    "            \n",
    " \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        # traverse the position where robot A makes a turn\n",
    "        # j = 0 ... n-1\n",
    "        # [0,j]      [j,n-1]\n",
    "        # s[0][:j+1] s[1][j:]\n",
    "        # 则robotB 剩下的选择是 max( s[0][j+1:], s[1][:j] )\n",
    "        n = len(grid[0])\n",
    "        ps0 = [0]*(n+1)\n",
    "        ps1 = [0]*(n+1)\n",
    "\n",
    "        for i in range(n):\n",
    "            ps0[i+1] = ps0[i] + grid[0][i]\n",
    "            ps1[i+1] = ps1[i] + grid[1][i]\n",
    "        \n",
    "        res = inf\n",
    "        for j in range(0, n):\n",
    "            # max( s[0][j+1:], s[1][:j] )\n",
    "            top = ps0[n] - ps0[j+1]\n",
    "            down = ps1[j]\n",
    "            res = min(res, max(top, down))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        top_prefix = [0] * (n+1)\n",
    "        bottom_prefix = [0] * (n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            top_prefix[i] = top_prefix[i+1] + grid[0][i]\n",
    "        for i in range(n):\n",
    "            bottom_prefix[i+1] = bottom_prefix[i] + grid[1][i]\n",
    "        \n",
    "        maxS = float('inf')\n",
    "        for i in range(n):\n",
    "            maxS = min(maxS, max(top_prefix[i+1], bottom_prefix[i]))\n",
    "        return maxS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        # 预处理前缀和\n",
    "        n = len(grid[0])\n",
    "        p = [[0] * (n + 1) for _ in range(2)]\n",
    "        for i in range(n):\n",
    "            p[0][i+1] = p[0][i] + grid[0][i]\n",
    "            p[1][i+1] = p[1][i] + grid[1][i]\n",
    "        # 枚举从那个点开始往下\n",
    "        ans = float('inf')\n",
    "        for i in range(n):\n",
    "            ans = min(ans, max(p[0][n] - p[0][i+1], p[1][i]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0]) #获取二维数组grid的列数n\n",
    "        prefix_sum_1 = [0] * (n+1) #第一行的前缀和数组\n",
    "        prefix_sum_2 = [0] * (n+1) #第二行的前缀和数组\n",
    "        for i in range(1, n+1):\n",
    "            prefix_sum_1[i] = prefix_sum_1[i-1] + grid[0][i-1]\n",
    "            prefix_sum_2[i] = prefix_sum_2[i-1] + grid[1][i-1]\n",
    "        ans = float('inf')\n",
    "        for i in range(n): # 枚举第一个机器人最后一次向右移动的位置\n",
    "            ans=min(ans,max(prefix_sum_1[-1]-prefix_sum_1[i+1],prefix_sum_2[i])) # 计算第二个机器人能够获得的最大点数，取最小值\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\r\n",
    "        pre_sum = [[0] * len(grid[0]) for _ in range(2)]\r\n",
    "        for i in range(2):\r\n",
    "            for j in range(len(grid[0])):\r\n",
    "                pre_sum[i][j] = grid[i][j] + (pre_sum[i][j-1] if j > 0 else 0)\r\n",
    "        res = float('inf')\r\n",
    "        for i in range(len(grid[0])):\r\n",
    "            res = min(res, max(pre_sum[0][-1] - pre_sum[0][i], pre_sum[1][i-1] if i > 0 else 0))\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        s = [[0] * (n+1) for _ in range(2)]\n",
    "        for i, (x, y) in enumerate(zip(*grid)):\n",
    "            s[0][i+1] = s[0][i] + x\n",
    "            s[1][i+1] = s[1][i] + y\n",
    "        # 枚举第一个机器人的拐点\n",
    "        # 第二个机器人能收集到的就是 下面的拐点之前的\n",
    "        # 或者是 上面的拐点之后的 都不包括拐点\n",
    "        return min(max(s[1][i] - s[1][0], s[0][n] - s[0][i+1]) for i in range(n))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        up = [0] * (1 + len(grid[0]))\n",
    "        down = [0] * (1 + len(grid[0]))\n",
    "        for i in range(len(grid[0])):\n",
    "            up[i+1] = up[i] + grid[0][i]\n",
    "            down[i+1] = down[i] + grid[1][i]\n",
    "        ans = inf\n",
    "        for i in range(len(grid[0])):\n",
    "            temp = max(down[i] - down[0], up[-1] - up[i+1])\n",
    "            ans = min(ans, temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        r1,r2 = [0]*n,[0]*n\n",
    "        for i in range(n-1,0,-1):r1[i-1] = r1[i]+grid[0][i]\n",
    "        for i in range(n-1):r2[i+1] = r2[i]+grid[1][i]\n",
    "        res = float('inf')\n",
    "        for i in range(n):res = min(res,max(r1[i],r2[i]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        r1,r2 = [0]*n,[0]*n\n",
    "        for i in range(n-1,0,-1):r1[i-1] = r1[i]+grid[0][i]\n",
    "        for i in range(n-1):r2[i+1] = r2[i]+grid[1][i]\n",
    "        res = float('inf')\n",
    "        for i in range(n):res = min(res,max(r1[i],r2[i]))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        res = float(\"inf\")\n",
    "        n = len(grid[0])\n",
    "        left_bottom = [0] * n \n",
    "        right_up = [0] * n \n",
    "        for i in range(1, n):\n",
    "            left_bottom[i] = left_bottom[i-1] + grid[1][i-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            right_up[i] = right_up[i+1] + grid[0][i+1]\n",
    "        \n",
    "        for i in range(n):\n",
    "            res = min(res,max(left_bottom[i],right_up[i]))\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0]) \n",
    "        prefix_sum_1 = [0] * (n+1) # 第一行的前缀和数组\n",
    "        prefix_sum_2 = [0] * (n+1) # 第二行的前缀和数组\n",
    "        for i in range(1, n+1):\n",
    "            prefix_sum_1[i] = prefix_sum_1[i-1] + grid[0][i-1]\n",
    "            prefix_sum_2[i] = prefix_sum_2[i-1] + grid[1][i-1]\n",
    "        \n",
    "        ans = float('inf')\n",
    "        for i in range(n): # 枚举第一个机器人最后一次向右移动的位置\n",
    "            ans = min(ans, max(prefix_sum_1[-1]-prefix_sum_1[i+1], prefix_sum_2[i])) # 计算第二个机器人能够获得的最大点数，取最小值\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        p = [[0] * (n + 1) for _ in range(2)]\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            p[0][i] = p[0][i - 1] + grid[0][i - 1]\n",
    "            p[1][i] = p[1][i - 1] + grid[1][i - 1]\n",
    "        \n",
    "        ans = float('inf')\n",
    "        for i in range(1, n + 1):\n",
    "            ans = min(ans, max(p[0][n] - p[0][i], p[1][i - 1]))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        # 预处理每一行的前缀和\n",
    "        n = len(grid[0])\n",
    "        g = [[0]*(n+1) for _ in range(2)]\n",
    "        for i in range(n):\n",
    "            g[0][i+1] = g[0][i]+grid[0][i]\n",
    "            g[1][i+1] = g[1][i]+grid[1][i]\n",
    "        # 枚举转折点\n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            ans = min(ans,max(g[0][n]-g[0][i+1],g[1][i]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        r1, r2 = [0] * n, [0] * n\n",
    "\n",
    "        for i in range(n-1, 0, -1):\n",
    "            r1[i-1] = r1[i] + grid[0][i]\n",
    "        for i in range(n-1):\n",
    "            r2[i+1] = r2[i] + grid[1][i]\n",
    "\n",
    "        res = float('INF')\n",
    "        for i in range(n):\n",
    "            res = min(res, max(r1[i], r2[i]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        r1,r2 = [0]*n,[0]*n\n",
    "        for i in range(n-1,0,-1):r1[i-1] = r1[i]+grid[0][i]\n",
    "        for i in range(n-1):r2[i+1] = r2[i]+grid[1][i]\n",
    "        res = float('inf')\n",
    "        for i in range(n):res = min(res,max(r1[i],r2[i]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        r1,r2 = [0]*n,[0]*n\n",
    "        for i in range(n-1,0,-1):r1[i-1] = r1[i]+grid[0][i]\n",
    "        for i in range(n-1):r2[i+1] = r2[i]+grid[1][i]\n",
    "        res = float('inf')\n",
    "        for i in range(n):res = min(res,max(r1[i],r2[i]))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        r1,r2 = [0]*n,[0]*n\n",
    "        for i in range(n-1,0,-1):r1[i-1] = r1[i]+grid[0][i]\n",
    "        for i in range(n-1):r2[i+1] = r2[i]+grid[1][i]\n",
    "        res = float('inf')\n",
    "        for i in range(n):res = min(res,max(r1[i],r2[i]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid[0])\n",
    "        f = [[0] * (m + 1) for i in range(3)]\n",
    "        for i in range(2):\n",
    "            for j in range(m):\n",
    "                f[i + 1][j + 1] = f[i + 1][j] + grid[i][j]\n",
    "        ret = 5 * 1E9 + 7\n",
    "        for i in range(m):\n",
    "            ret = min(ret, max(f[2][i], f[1][m] - f[1][i + 1]))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        r1, r2 = [0] * n, [0] * n\n",
    "        for i in range(n - 1, 0, -1): r1[i - 1] = r1[i] + grid[0][i]\n",
    "        for i in range(n - 1): r2[i + 1] = r2[i] + grid[1][i]\n",
    "        res = float('inf')\n",
    "        for i in range(n): res = min(res, max(r1[i], r2[i]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        r1,r2 = [0]*n,[0]*n\n",
    "        for i in range(n-1,0,-1):r1[i-1] = r1[i]+grid[0][i]\n",
    "        for i in range(n-1):r2[i+1] = r2[i]+grid[1][i]\n",
    "        res = float('inf')\n",
    "        for i in range(n):res = min(res,max(r1[i],r2[i]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        res = 1000000000000\n",
    "        x = [0] * n\n",
    "        y = [0] * n\n",
    "\n",
    "        x[0] = grid[0][0]\n",
    "        y[0] = grid[1][0]\n",
    "        for i in range(1, n):\n",
    "            x[i] = x[i - 1] + grid[0][i]\n",
    "            y[i] = y[i - 1] + grid[1][i]\n",
    "        \n",
    "        for i in range(n):\n",
    "            # res = min({res, x[n - 1] - x[i], y[i - 1]})\n",
    "            if i:\n",
    "                res = min(res, max(x[n - 1] - x[i], y[i - 1]));\n",
    "            else:\n",
    "                res = min(res, max(x[n - 1] - x[i], 0));\n",
    "\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        sum0,sum1 = [],[]\n",
    "        sum_0,sum_1 = 0,0\n",
    "        for i in range(len(grid[0])):\n",
    "            sum_0 += grid[0][i]\n",
    "            sum_1 += grid[1][i]\n",
    "            sum0.append(sum_0)\n",
    "            sum1.append(sum_1)\n",
    "        min_ = sum0[-1]-sum0[0]\n",
    "        for i in range(len(grid[0])):\n",
    "            t0 = sum0[-1] - sum0[i]\n",
    "            t1 = sum1[i-1] if i-1>=0 else 0\n",
    "            if max(t0,t1) < min_:\n",
    "                min_ = max(t0,t1)\n",
    "        return min_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        pre,suf = [0],[0]\n",
    "        n = len(grid[0])\n",
    "        for i in range(n):\n",
    "            pre.append(pre[-1] + grid[1][i])\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            suf.append(suf[-1] + grid[0][i])\n",
    "        suf.reverse()\n",
    "        ans = float('inf')\n",
    "     \n",
    "        for i in range(n):\n",
    "            #左侧剩余分数\n",
    "            lleft = pre[i]\n",
    "            # 右侧剩余分数\n",
    "            rleft = suf[i + 1]\n",
    "            ans = min(ans,max(lleft,rleft))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        ans = inf\n",
    "        ps1, ps2 = list(accumulate(grid[0], initial=0)), list(accumulate(grid[1], initial=0))\n",
    "\n",
    "        for i in range(n):\n",
    "            ans = min(ans, max(ps1[-1] - ps1[i + 1], ps2[i]))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        Col = len(grid[0]) # 获取二维数组的列数\n",
    "        presum1 = [0 for _ in range(Col + 1)] # 创建第一行的前缀和数组\n",
    "        for c in range(Col):\n",
    "            presum1[c+1] = presum1[c] + grid[0][c] # 计算前缀和\n",
    "        presum2 = [0 for _ in range(Col + 1)] # 创建第二行的前缀和数组\n",
    "        for c in range(Col):\n",
    "            presum2[c+1] = presum2[c] + grid[1][c] # 计算前缀和\n",
    "        \n",
    "        res = float('inf') # 初始化结果为正无穷大\n",
    "        for mid in range(Col): # 遍历中间划分的位置\n",
    "            up = presum1[Col] - presum1[mid + 1] # 计算上半部分的和\n",
    "            down = presum2[mid] # 计算下半部分的和\n",
    "            res = min(res, max(up, down)) # 更新结果为上下两部分的最大值\n",
    "        return res # 返回结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        row1 = grid[0]\n",
    "        row2 = grid[1]\n",
    "        pre1 = list(accumulate(row1, initial=0))\n",
    "        pre2 = list(accumulate(row2, initial=0))\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            v = max(pre1[-1]-pre1[i+1], pre2[i])\n",
    "            ans = min(ans, v)\n",
    "        \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        row1 = [0 for _ in range(n+1)]\n",
    "        row2 = [0 for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            row1[i] = row1[i-1] + grid[0][i-1]\n",
    "            row2[i] = row2[i-1] + grid[1][i-1]\n",
    "        res = float('inf')\n",
    "        for i in range(1, n+1):\n",
    "            rest1 = row1[n]-row1[i]\n",
    "            rest2 = row2[i-1]\n",
    "            res = min(res, max(rest1, rest2))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        ans = inf\n",
    "        s1 = list(accumulate(grid[0], initial=0))\n",
    "        s2 = list(accumulate(grid[1], initial=0))\n",
    "        for i in range(1, n + 1):\n",
    "            ans = min(ans, max(s2[i - 1], s1[n] - s1[i]))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        pre1 = list(accumulate(grid[0], initial=0))\n",
    "        pre2 = list(accumulate(grid[1], initial=0))\n",
    "        \n",
    "        ans = inf\n",
    "        n = len(grid[0])\n",
    "        for i in range(n):\n",
    "            cur = max(pre1[-1] - pre1[i+1], pre2[i])\n",
    "            if cur < ans:\n",
    "                ans = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, G: List[List[int]]) -> int:\n",
    "        T = [0] + list(accumulate(G[0]))\n",
    "        B = [0] + list(accumulate(G[1]))\n",
    "        return min(max(T[len(T) - 1] - T[i], B[i-1]) for i in range(1, len(T)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid[0])\n",
    "        pre1 = [0]\n",
    "        pre2 = [0]\n",
    "        for k in range(m):\n",
    "            pre1.append(pre1[-1] + grid[0][k])\n",
    "            pre2.append(pre2[-1] + grid[1][k])\n",
    "        ans = float('inf')\n",
    "        for k in range(1, m+1):\n",
    "            cur = max(pre1[-1]-pre1[k], pre2[k-1])\n",
    "            ans = min(ans, cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        ans = inf\n",
    "        s1 = list(accumulate(grid[0], initial=0)) #第一行前缀和\n",
    "        s2 = list(accumulate(grid[1], initial=0)) #第二行前缀和\n",
    "        for i in range(1, n + 1):\n",
    "            #第一个人选择一个位置i往下走\n",
    "            #会使得第二行1~i-1和第一行i+1~n都为0\n",
    "            #第二个人一定会选择最左或最右的位置往下\n",
    "            ans = min(ans, max(s2[i - 1], s1[n] - s1[i]))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        if len(grid[0]) == 1:\n",
    "            return 0\n",
    "        first_sum = [ 0 ]\n",
    "        second_before_sum = [ 0 ]\n",
    "        for i in grid[0][:0:-1]:\n",
    "            first_sum.insert(0,first_sum[0] + i )\n",
    "        for i in grid[1][:-1]:\n",
    "            second_before_sum.append(second_before_sum[-1] + i)\n",
    "        res = inf \n",
    "        for i in range(len(first_sum)):\n",
    "            tmp_max_score = max( first_sum[i] , second_before_sum[i])\n",
    "            if tmp_max_score < res:\n",
    "                res = tmp_max_score\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        m = 2\n",
    "        n = len(grid[0])\n",
    "        presum = [[0],[0]]\n",
    "        for j in range(n):\n",
    "            presum[0].append(presum[0][-1]+grid[0][j])\n",
    "            presum[1].append(presum[1][-1]+grid[1][j])\n",
    "        result = float('inf')\n",
    "        for j in range(n):\n",
    "            result = min(result, max(presum[0][-1]-presum[0][j+1], presum[1][j]))\n",
    "        return result\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        m = 2\n",
    "        n = len(grid[0])\n",
    "        presum = [[0],[0]]\n",
    "        for j in range(n):\n",
    "            presum[0].append(presum[0][-1]+grid[0][j])\n",
    "            presum[1].append(presum[1][-1]+grid[1][j])\n",
    "        result = float('inf')\n",
    "        for j in range(n):\n",
    "            result = min(result, max(presum[0][-1]-presum[0][j+1], presum[1][j]))\n",
    "        return result\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        m = 2\n",
    "        n = len(grid[0])\n",
    "        presum = [[0],[0]]\n",
    "        for j in range(n):\n",
    "            presum[0].append(presum[0][-1]+grid[0][j])\n",
    "            presum[1].append(presum[1][-1]+grid[1][j])\n",
    "        result = float('inf')\n",
    "        for j in range(n):\n",
    "            result = min(result, max(presum[0][-1]-presum[0][j+1], presum[1][j]))\n",
    "        return result\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        s0, s1 = [0] + list(accumulate(grid[0])), [0] + list(accumulate(grid[1]))\n",
    "        return reduce(lambda ans, i: min(ans, max(s0[-1] - s0[i], s1[i - 1] - s1[0])), range(1, len(s0)), float('inf'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        s = [[0 for i in range(len(grid[0])+1)] for _ in range(2)]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                s[i][j+1] = grid[i][j] + s[i][j]\n",
    "        return min([max(s[1][i],s[0][-1]-s[0][i+1]) for i in range(len(grid[0]))])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        s0, s1 = [0] + list(accumulate(grid[0])), [0] + list(accumulate(grid[1]))\n",
    "        return reduce(lambda ans, i: min(ans, max(s0[-1] - s0[i], s1[i - 1] - s1[0])), range(1, len(s0)), float('inf'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        N, up, down = len(grid[0]), [grid[0][-1]], [grid[1][0]]\n",
    "        for i in range(1, N):\n",
    "            up.append(up[-1] + grid[0][N - 1 - i])\n",
    "            down.append(down[-1] + grid[1][i])\n",
    "\n",
    "        return min([max(up[N - i - 2] if i < N - 1 else 0, down[i - 1] if i > 0 else 0) for i in range(N)])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        s = [[0] * (n + 1), [0] * (n + 1)]\n",
    "        tot = 0\n",
    "        for i in range(2):\n",
    "            for j in range(n):\n",
    "                s[i][j + 1] = s[i][j] + grid[i][j]\n",
    "                tot += grid[i][j]\n",
    "        print(s[0], s[1])\n",
    "        mx = 10 ** 10\n",
    "        for i in range(n):\n",
    "            mx = min(mx, max(s[0][n] - s[0][i + 1], s[1][i]))  \n",
    "        return mx\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        # 博弈dp\n",
    "        # 如果单纯收集最大点数，只需对比四个格子当中的内容选出最大的收集并且继续进行游戏即可\n",
    "        # 注意到了仅有两排格子\n",
    "        # 只需选择在哪里转换即可\n",
    "        # 第一个前缀加上第二个后缀的最大值（第一个得分最大），第二个机器人收集的元素是第一个机器人选剩下的\n",
    "        prefix1 = [0]*len(grid[0])\n",
    "        prefix2 = [0]*len(grid[0])\n",
    "        prefix1[0] = grid[0][0]\n",
    "        prefix2[-1] = grid[1][-1]\n",
    "\n",
    "        for i in range(1,len(prefix1)):\n",
    "            prefix1[i] = prefix1[i-1] + grid[0][i]\n",
    "        \n",
    "        for i in range(len(prefix2)-2,-1,-1):\n",
    "            prefix2[i] = prefix2[i+1] + grid[1][i]\n",
    "        \n",
    "        # 第一个机器人选择向下的位置\n",
    "        # dp1 = [0]*len(prefix1)\n",
    "        dp2 = [0]*len(prefix1)\n",
    "        res = inf \n",
    "        for i in range(len(dp2)):\n",
    "            # dp1[i] = prefix1[i] + prefix2[i]\n",
    "            dp2[i] = max(prefix1[-1]-prefix1[i],prefix2[0]-prefix2[i])\n",
    "            res = min(res,dp2[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        arr = [0]\n",
    "        n = len(grid[0])\n",
    "        for row in grid:\n",
    "            for c in row:\n",
    "                arr.append(arr[-1] + c)\n",
    "        return min([max(arr[k + n - 1] - arr[n], arr[n] - arr[k]) for k in range(1, n + 1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        arr = [0]\n",
    "        n = len(grid[0])\n",
    "        for row in grid:\n",
    "            for c in row:\n",
    "                arr.append(arr[-1] + c)\n",
    "        return min([max(arr[k + n - 1] - arr[n], arr[n] - arr[k]) for k in range(1, n + 1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "        _len=len(grid[0])\n",
    "        # 结果= max(行1的后置和, 行2的前置和)\n",
    "        suf_sum=[0]*(_len+1) # n_i=s_i-s_i+1\n",
    "        pre_sum = [0] * (_len + 1)  # n_i=s_i+1-s_i\n",
    "        for _,num in reversed(list(enumerate(grid[0]))):\n",
    "            suf_sum[_]=suf_sum[_+1]+num\n",
    "\n",
    "        for _, num in enumerate(grid[1]):\n",
    "            pre_sum[_+1]=pre_sum[_]+num\n",
    "        result=max(pre_sum[_len],suf_sum[0])\n",
    "        for _ in range(_len):\n",
    "            _result=max(pre_sum[_],suf_sum[_+1])\n",
    "            if _result<result:\n",
    "                result=_result\n",
    "        return result\n",
    "if __name__ == '__main__':\n",
    "    print(Solution().gridGame([[1,3,1,15],[1,3,3,1]]))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
